{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Alternating Subarray Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumAlternatingSubarraySum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大交替子数组和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>子数组</strong>是以<strong>0</strong>下标开始的数组的连续非空子序列，从 <code>i</code> 到 <code>j</code>（<code>0 &lt;= i &lt;= j &lt; nums.length</code>）的 <strong>子数组交替和</strong> 被定义为 <code>nums[i] - nums[i+1] + nums[i+2] - ... +/- nums[j]</code> 。</p>\n",
    "\n",
    "<p>给定一个以<strong>0</strong>下标开始的整数数组<code>nums</code>，返回它所有可能的交替子数组和的最大值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,-1,1,2]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "子数组 [3,-1,1]有最大的交替子数组和3 - (-1) + 1 = 5.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,2,2,2,2]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "子数组 [2], [2,2,2]和 [2,2,2,2,2]有相同的最大交替子数组和为2\n",
    "[2]: 2.\n",
    "[2,2,2]: 2 - 2 + 2 = 2.\n",
    "[2,2,2,2,2]: 2 - 2 + 2 - 2 + 2 = 2.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "仅有一个非空子数组，为 [1]，它的交替子数组和为 1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-alternating-subarray-sum](https://leetcode.cn/problems/maximum-alternating-subarray-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-alternating-subarray-sum](https://leetcode.cn/problems/maximum-alternating-subarray-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,-1,1,2]', '[2,2,2,2,2]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        plu, minu = nums[0], -inf\n",
    "        ans = plu\n",
    "        for x in nums[1:]:\n",
    "            plu, minu = max(x, x + minu), plu - x \n",
    "            ans = max(ans, plu, minu)\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "      jia = nums[0]\n",
    "      jian = 0\n",
    "      ans = jia\n",
    "      for i in range(1,len(nums)):\n",
    "        j = nums[i]\n",
    "        jia,jian = max(j,jian+j),jia-j\n",
    "        ans = max(jia,jian,ans)\n",
    "      return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        ans = nums[0]\n",
    "        pos, neg = nums[0], 0\n",
    "        for i in range(1, len(nums)):\n",
    "            npos, nneg = max(nums[i], neg+nums[i]), pos - nums[i]\n",
    "            pos, neg = npos, nneg\n",
    "            ans = max(ans, max(pos, neg))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "      jia = nums[0]\n",
    "      jian = -inf\n",
    "      ans = jia\n",
    "      for i in range(1,len(nums)):\n",
    "        j = nums[i]\n",
    "        jia,jian = max(j,jian+j),jia-j\n",
    "        ans = max(jia,jian,ans)\n",
    "      return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp0, dp1 = 0, nums[0]\n",
    "        ans = dp1\n",
    "        for i in range(1,n):\n",
    "            dp0,dp1 = max(0, dp1-nums[i]), dp0+nums[i]\n",
    "            ans = max(ans, dp0, dp1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp0, dp1 = 0, nums[0]\n",
    "        ans = dp1\n",
    "        for i in range(1,n):\n",
    "            dp0,dp1 = dp1-nums[i], max(dp0+nums[i], nums[i])\n",
    "            ans = max(ans, dp0, dp1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [-inf] * n     ## 偶数\n",
    "        g = [-inf] * n     ## 奇数\n",
    "        g[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            f[i] = g[i-1] - nums[i]\n",
    "            g[i] = max(f[i-1] + nums[i], nums[i])\n",
    "        return max(max(f), max(g))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp1 = [0] * n \n",
    "        dp2 = [0] * n \n",
    "        dp1[0] = nums[0]\n",
    "        ans = nums[0] \n",
    "        for i in range(1, n):\n",
    "            dp1[i] = max(dp2[i-1] + nums[i], nums[i])\n",
    "            dp2[i] = dp1[i-1] - nums[i] \n",
    "            ans = max(ans, max(dp1[i], dp2[i]))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "      if len(nums) == 1:\n",
    "        return nums[0]\n",
    "      dpp, dpm = [0] * len(nums), [0] * len(nums)\n",
    "      dpp[0] = nums[0]\n",
    "      dpm[0] = 0\n",
    "      for i in range(1, len(nums)):\n",
    "        dpp[i] = dpm[i - 1] + nums[i] if dpm[i - 1] > 0 else nums[i]\n",
    "        dpm[i] = dpp[i - 1] - nums[i]\n",
    "      return max(dpp + dpm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        dp,ans=[[nums[0],0]],nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            left=max(dp[-1][1]+nums[i],nums[i])\n",
    "            right=dp[-1][0]-nums[i]\n",
    "            dp.append([left,right])\n",
    "            ans=max(ans,left,right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "\n",
    "        dp=[[-float(\"inf\")]*2 for _ in range(n)]\n",
    "        dp[0][0]=-float(\"inf\")\n",
    "        dp[0][1]=nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=dp[i-1][1]-nums[i]\n",
    "            dp[i][1]=max(dp[i-1][0]+nums[i],nums[i])\n",
    "        \n",
    "        res=-float(\"inf\")\n",
    "        for x in dp:\n",
    "            if max(x)>res:\n",
    "                res=max(x)\n",
    "        return res\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 动态规划（类似股票交易）\n",
    "    # dp[i][0]表示以i结尾的子数组最后操作为-的结果\n",
    "    # dp[i][1]表示以i结尾的子数组最后操作为+的结果\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[[-inf]*2 for _ in range(n)]\n",
    "        dp[0][1]=nums[0]\n",
    "        dp[0][0]=0\n",
    "        res=nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=dp[i-1][1]-nums[i]\n",
    "            dp[i][1]=max(dp[i-1][0]+nums[i],nums[i])\n",
    "            res=max(res,max(dp[i]))\n",
    "\n",
    "        return res\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[[-inf]*2 for _ in range(n)]\n",
    "        dp[0][1]=nums[0]\n",
    "        dp[0][0]=0\n",
    "        res=nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=dp[i-1][1]-nums[i]\n",
    "            dp[i][1]=max(dp[i-1][0]+nums[i],nums[i])\n",
    "            res=max(res,max(dp[i]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[[-inf]*2 for _ in range(n)]\n",
    "        dp[0][1]=nums[0]\n",
    "        dp[0][0]=0\n",
    "        res=nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=dp[i-1][1]-nums[i]\n",
    "            dp[i][1]=max(dp[i-1][0]+nums[i],nums[i])\n",
    "            res=max(res,max(dp[i]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[[-float('inf')]*2 for _ in range(n)]\n",
    "        dp[0][1]=nums[0]\n",
    "        dp[0][0]=0\n",
    "        ans=nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][1]=max(nums[i],dp[i-1][0]+nums[i])\n",
    "            dp[i][0]=dp[i-1][1]-nums[i]\n",
    "\n",
    "            ans=max(ans,max(dp[i]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[[-inf]*2 for _ in range(n)]\n",
    "        dp[0][1]=nums[0]\n",
    "        dp[0][0]=0\n",
    "        res=nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=dp[i-1][1]-nums[i]\n",
    "            dp[i][1]=max(dp[i-1][0]+nums[i],nums[i])\n",
    "            res=max(res,max(dp[i]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 动态规划（类似股票交易）\n",
    "    # dp[i][0]表示以i结尾的子数组最后操作为-的结果\n",
    "    # dp[i][1]表示以i结尾的子数组最后操作为+的结果\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[-inf] * 2 for _ in range(n)]\n",
    "        dp[0][1] = nums[0]\n",
    "        dp[0][0] = 0\n",
    "        res = nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] = dp[i-1][1] - nums[i]\n",
    "            dp[i][1] = max(dp[i-1][0] + nums[i], nums[i])\n",
    "            res = max(res, max(dp[i]))\n",
    "\n",
    "        return res\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp=[[-inf]*2 for _ in range(n)]\n",
    "        dp[0][1]=nums[0]\n",
    "        dp[0][0]=0\n",
    "        res=nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] = dp[i-1][1] - nums[i]\n",
    "            dp[i][1]=max(dp[i-1][0]+nums[i],nums[i])\n",
    "            res=max(res,max(dp[i]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[-inf] * 2 for _ in range(n)]\n",
    "        dp[0][1] = nums[0]\n",
    "        dp[0][0] = 0\n",
    "        res = nums[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][1] - nums[i]\n",
    "            dp[i][1] = max(dp[i-1][0] + nums[i], nums[i])\n",
    "            res = max(res, max(dp[i]))\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
